import java.util.List;
import java.util.TreeSet;

// 最小区间
// 你有k个非递减排列的整数列表
// 找到一个最小区间，使得k个列表中的每个列表至少有一个数包含在其中
// 测试链接 : https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/
public class Code02_SmallestRange {

    public static class Node {
        public int v; // 值
        public int i; // 当前值来自哪个数组
        public int j; // 当前值来自i号数组的什么位置

        public Node(int a, int b, int c) {
            v = a;
            i = b;
            j = c;
        }
    }

    // 时间复杂度O(n*logk)
    // n是数字总数，k是数组数量
    public static int[] smallestRange(List<List<Integer>> nums) {
        int k = nums.size();
        // 根据值排序
        // 为什么排序的时候i要参与
        // 因为有序表中比较相等的样本只会保留一个
        // 为了值一样的元素都保留，于是i要参与排序
        // 在有序表中的所有元素i必然都不同
        TreeSet<Node> set = new TreeSet<>((a, b) -> a.v != b.v ? (a.v - b.v) : (a.i - b.i));
        for (int i = 0; i < k; i++) {
            set.add(new Node(nums.get(i).get(0), i, 0));
        }
        int r = Integer.MAX_VALUE; // 记录最窄区间的宽度
        int a = 0; // 记录最窄区间的开头
        int b = 0; // 记录最窄区间的结尾
        Node max, min;
        while (set.size() == k) {
            max = set.last(); // 在有序表中，值最大的记录
            min = set.pollFirst(); // 在有序表中，值最小的记录，并弹出
            if (max.v - min.v < r) {
                r = max.v - min.v;
                a = min.v;
                b = max.v;
            }
            if (min.j + 1 < nums.get(min.i).size()) {
                set.add(new Node(nums.get(min.i).get(min.j + 1), min.i, min.j + 1));
            }
        }
        return new int[] { a, b };
    }

}